// 给定两个有序数组nums1和nums2，将nums2合并到nums1，使nums1成为一个有序数组

// 思路，从后往前分别遍历nums1和nums2，分别用index1和index2指向当前比较的元素，index指向当前填充的位置
// 时间复杂度：O(m+n)
// 空间复杂度：O(1)
function merge(arr1, m, arr2, n) {
    let index1 = m - 1
    let index2 = n - 1
    let index = m + n - 1
    while (index1 >= 0 && index2 >= 0) {
        if (arr1[index1] < arr2[index2]) {
            arr1[index] = arr2[index2]
            index2--
        } else {
            arr1[index] = arr1[index1]
            index1--
        }
        index--
    }
    // 这里需要注意别漏掉index2没有遍历完的情况
    while (index2 >= 0) {
        arr1[index] = arr2[index2]
        index2--
        index--
    }
}